/**
 * @Author Fizz Pu
 * @Date 2020/10/22 下午6:07
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

/**
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
 *
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
 *
 * 问总共有多少条不同的路径？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/unique-paths
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

// 第一反应 可以递归解决这个问题，走到终点就两种走法,但是超时了

import java.util.Arrays;
import java.util.UUID;

/**
 * * * *
 * * * *
 * * * *
 */

// * * * *

public class Lee62 {

    public int uniquePaths(int m, int n) {
        /*if(m == 1 || n == 1 )return 1;
        return uniquePaths(m-1, n) + uniquePaths(m, n -1);
        int[][] dp = new int[m][n];
        for(int col = 0; col < n; ++col)dp[0][col] = 1;
        for(int row = 0; row < m; ++row)dp[row][0] = 1;
        for(int i = 1; i < m; ++i){
            for(int j = 1; j < n; ++j){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
         */
        int[] dp = new int[n+1];
        Arrays.fill(dp,1, n+1, 1);
        for(int i = 1; i < m; ++i){
            for(int j = 1; j < n + 1; ++j)
            dp[j] = dp[j-1] + dp[j];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Lee62 lee62 = new Lee62();
        System.out.println(lee62.uniquePaths(3,7));
    }
}
